{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Four Divisors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumFourDivisors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #四因数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [21,4,7]\n",
    "<strong>输出：</strong>32\n",
    "<strong>解释：</strong>\n",
    "21 有 4 个因数：1, 3, 7, 21\n",
    "4 有 3 个因数：1, 2, 4\n",
    "7 有 2 个因数：1, 7\n",
    "答案仅为 21 的所有因数的和。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [21,21]\n",
    "<strong>输出:</strong> 64\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,4,5]\n",
    "<strong>输出:</strong> 0</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [four-divisors](https://leetcode.cn/problems/four-divisors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [four-divisors](https://leetcode.cn/problems/four-divisors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[21,4,7]', '[21,21]', '[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        dic = []\n",
    "        for num in nums:\n",
    "            temp = set()\n",
    "            for i in range(1, int(math.sqrt(num)) + 1):\n",
    "                if num % i == 0:\n",
    "                    temp.add(i)\n",
    "                    temp.add(num // i)\n",
    "            if len(temp) == 4:\n",
    "                ans += sum(temp)\n",
    "                dic.append(num)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def is_four(num):\n",
    "            \n",
    "            e = int(math.sqrt(num)) + 1\n",
    "            for i in range(2, e):\n",
    "                if num % i == 0:\n",
    "                    s = num // i\n",
    "                    if s == i:\n",
    "                        return False\n",
    "                    if s == i ** 2:\n",
    "                        return i + s + num + 1\n",
    "                    for j in range(i, int(math.sqrt(s)) + 1):\n",
    "                        if s % j == 0:\n",
    "                            return False\n",
    "                    else:\n",
    "                        return i + s + num + 1\n",
    "                        \n",
    "        r = 0\n",
    "        for i in nums:\n",
    "            ret = is_four(i)\n",
    "            if ret:\n",
    "                r += ret\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def is_four(num):\n",
    "            \n",
    "            for i in range(2, int(math.sqrt(num)) + 1):\n",
    "                if num % i == 0:\n",
    "                    s = num // i\n",
    "                    if s == i:\n",
    "                        return False\n",
    "                    if s == i ** 2:\n",
    "                        return i + s + num + 1\n",
    "                    for j in range(i, int(math.sqrt(s)) + 1):\n",
    "                        if s % j == 0:\n",
    "                            return False\n",
    "                    else:\n",
    "                        return i + s + num + 1\n",
    "                        \n",
    "        r = 0\n",
    "        for i in nums:\n",
    "            ret = is_four(i)\n",
    "            if ret:\n",
    "                r += ret\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            p = -1\n",
    "            for a in range(2, int(sqrt(n)) + 1):\n",
    "                if n % a == 0:\n",
    "                    if p != -1:\n",
    "                        break\n",
    "                    p = a\n",
    "            else:\n",
    "                if p * p != n:\n",
    "                    res += n + 1 + p + n // p\n",
    "            continue\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            if is_target(n):\n",
    "                ans += is_target(n)\n",
    "\n",
    "        return ans\n",
    "\n",
    "def is_target(n: int):\n",
    "    if n < 3:\n",
    "        return False\n",
    "    if int(n**0.5) ** 2 == n:\n",
    "        return False\n",
    "    ans = [1, n]\n",
    "    for i in range(2, int(n ** 0.5)+1):\n",
    "        if n % i == 0:\n",
    "            ans.append(i)\n",
    "            ans.append(n // i)\n",
    "        if len(ans) > 4:\n",
    "            return False\n",
    "    if len(ans) == 2:\n",
    "        return False\n",
    "\n",
    "    # print(ans)\n",
    "    return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        dic = []\n",
    "        for num in nums:\n",
    "            temp = set()\n",
    "            for i in range(1, int(math.sqrt(num)) + 1):\n",
    "                if num % i == 0:\n",
    "                    temp.add(i)\n",
    "                    temp.add(num // i)\n",
    "                if len(temp) > 4:\n",
    "                    break\n",
    "            if len(temp) == 4:\n",
    "                ans += sum(temp)\n",
    "                dic.append(num)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for num in nums :\n",
    "            result += self.find_divisors(num)\n",
    "            pass\n",
    "        return result\n",
    "        pass\n",
    "\n",
    "    def find_divisors(self, num):\n",
    "\n",
    "        cached = set()\n",
    "        end = int(math.sqrt(num)) + 1\n",
    "\n",
    "        for i in range(1,end) :\n",
    "            if num % i == 0 :\n",
    "                cached.add(i)\n",
    "                cached.add(num // i)\n",
    "            if len(cached) > 4 :\n",
    "                return 0\n",
    "            pass\n",
    "        return sum(cached) if len(cached) == 4 else 0\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        \n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            val = n ** 0.5\n",
    "            if int(val) == val:\n",
    "                continue\n",
    "\n",
    "            i = 1\n",
    "            tmp = 0\n",
    "            sum_ = 0\n",
    "            flag = True\n",
    "            while i * i <= n:\n",
    "                if n % i == 0:\n",
    "                    sum_ += i \n",
    "                    sum_ += n // i\n",
    "                    tmp += 2\n",
    "                    if tmp > 4:\n",
    "                        flag = False\n",
    "                        break\n",
    "                i += 1\n",
    "\n",
    "            if flag and tmp == 4:\n",
    "                res += sum_\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            # factor_cnt: 因数的个数\n",
    "            # factor_sum: 因数的和\n",
    "            factor_cnt = factor_sum = 0\n",
    "            i = 1\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    factor_cnt += 1\n",
    "                    factor_sum += i\n",
    "                    if i * i != num:   # 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数\n",
    "                        factor_cnt += 1\n",
    "                        factor_sum += num // i\n",
    "                i += 1\n",
    "            if factor_cnt == 4:\n",
    "                ans += factor_sum\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# MX = 10001\n",
    "# isPrime = [True] * MX\n",
    "# for i in range(2, MX):\n",
    "#     if isPrime[i]:\n",
    "#         for j in range(i * i, MX, i):\n",
    "#             isPrime[j] = False\n",
    "# isPrime[0] = isPrime[1] = False\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            st = {1, x}\n",
    "            for i in range(2, int(x ** 0.5) + 1):\n",
    "                if x % i == 0:\n",
    "                    st.add(i)\n",
    "                    st.add(x // i)\n",
    "            if len(st) == 4:\n",
    "                ans += sum(st)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            temp = set()\n",
    "            for i in range(1, int(math.sqrt(num)) + 1):\n",
    "                if num % i == 0:\n",
    "                    temp.add(i)\n",
    "                    temp.add(num // i)\n",
    "                if len(temp) > 4:\n",
    "                    break\n",
    "            if len(temp) == 4:\n",
    "                ans += sum(temp)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "import math\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\r\n",
    "        def is_four(num):\r\n",
    "            \r\n",
    "            e = int(math.sqrt(num)) + 1\r\n",
    "            for i in range(2, e):\r\n",
    "                if num % i == 0:\r\n",
    "                    s = num // i\r\n",
    "                    if s == i:\r\n",
    "                        return False\r\n",
    "                    if s == i ** 2:\r\n",
    "                        return i + s + num + 1\r\n",
    "                    for j in range(i, int(math.sqrt(s)) + 1):\r\n",
    "                        if s % j == 0:\r\n",
    "                            return False\r\n",
    "                    else:\r\n",
    "                        return i + s + num + 1\r\n",
    "                        \r\n",
    "        r = 0\r\n",
    "        for i in nums:\r\n",
    "            ret = is_four(i)\r\n",
    "            if ret:\r\n",
    "                r += ret\r\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def fourDivisors(num):\n",
    "            divisors = set()\n",
    "            a, b = 2, int(sqrt(num))\n",
    "            while a <= b:\n",
    "                if num%a == 0:\n",
    "                    divisors.add(a)\n",
    "                    if a != num//a:\n",
    "                        divisors.add(num//a)\n",
    "                a += 1\n",
    "            return divisors\n",
    "        res_sum = 0\n",
    "        for item in nums:\n",
    "            divisors = fourDivisors(item)\n",
    "            if len(divisors) == 2:\n",
    "                res_sum = res_sum + sum(divisors) + item + 1\n",
    "        return res_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            # factor_cnt: 因数的个数\n",
    "            # factor_sum: 因数的和\n",
    "            factor_cnt = factor_sum = 0\n",
    "            i = 1\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    factor_cnt += 1\n",
    "                    factor_sum += i\n",
    "                    if i * i != num:   # 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数\n",
    "                        factor_cnt += 1\n",
    "                        factor_sum += num // i\n",
    "                i += 1\n",
    "            if factor_cnt == 4:\n",
    "                ans += factor_sum\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def isFourDivisor(num):\n",
    "            s = set()\n",
    "            for i in range(1, int(math.sqrt(num)) + 1):\n",
    "                if num % i == 0:\n",
    "                    s.add(i)\n",
    "                    s.add(num // i)\n",
    "            if len(s) == 4:\n",
    "                return sum(s)\n",
    "            else:\n",
    "                return 0\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += isFourDivisor(num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            # factor_cnt: 因数的个数\n",
    "            # factor_sum: 因数的和\n",
    "            factor_cnt = factor_sum = 0\n",
    "            i = 1\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    factor_cnt += 1\n",
    "                    factor_sum += i\n",
    "                    if i * i != num:   # 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数\n",
    "                        factor_cnt += 1\n",
    "                        factor_sum += num // i\n",
    "                i += 1\n",
    "            if factor_cnt == 4:\n",
    "                ans += factor_sum\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def get_divisors(num: int) -> List[int]:\n",
    "            divisors = []\n",
    "            for i in range(1, int(num ** 0.5) + 1):\n",
    "                if num % i == 0:\n",
    "                    divisors.append(i)\n",
    "                    if i != num // i:\n",
    "                        divisors.append(num // i)\n",
    "                if len(divisors) > 4:\n",
    "                    return []\n",
    "            return divisors if len(divisors) == 4 else []\n",
    "\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans += sum(get_divisors(num))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        MAX_PRIME = 10000\n",
    "        is_prime = [1]*MAX_PRIME\n",
    "        prime = [1]\n",
    "        for i in range(2, MAX_PRIME):\n",
    "            if is_prime[i] == 1:\n",
    "                prime.append(i)\n",
    "                tmp = i*2\n",
    "                while(tmp < MAX_PRIME):\n",
    "                    is_prime[tmp] = 0\n",
    "                    tmp += i\n",
    "        \n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            tmp = []\n",
    "            for p in range(1, 1 + int(math.sqrt(x))):\n",
    "                if x%p == 0:\n",
    "                    tmp.append(p)\n",
    "                    tmp.append(x//p)\n",
    "            if len(tmp) == 4 and int(math.sqrt(x))**2 != x:\n",
    "                ans += sum(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            # factor_cnt: 因数的个数\n",
    "            # factor_sum: 因数的和\n",
    "            factor_cnt = factor_sum = 0\n",
    "            i = 1\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    factor_cnt += 1\n",
    "                    factor_sum += i\n",
    "                    if i * i != num:   # 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数\n",
    "                        factor_cnt += 1\n",
    "                        factor_sum += num // i\n",
    "                i += 1\n",
    "            if factor_cnt == 4:\n",
    "                ans += factor_sum\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            if is_target(n):\n",
    "                ans += is_target(n)\n",
    "\n",
    "        return ans\n",
    "\n",
    "def is_target(n: int):\n",
    "    if n < 3:\n",
    "        return False\n",
    "    if int(n**0.5) ** 2 == n:\n",
    "        return False\n",
    "    ans = [1, n]\n",
    "    for i in range(2, int(n ** 0.5)+1):\n",
    "        if n % i == 0:\n",
    "            ans.append(i)\n",
    "            ans.append(n // i)\n",
    "        if len(ans) > 4:\n",
    "            return False\n",
    "    if len(ans) == 2:\n",
    "        return False\n",
    "\n",
    "    # print(ans)\n",
    "    return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def cf(n):\n",
    "            li = []                             #创建空列表用于存储因数\n",
    "            for i in range(1, int(n**0.5) + 1): #因数从一开始算，算到原本的数的平方根停止\n",
    "                if n % i == 0:                  #检测是i是否能被n整除（是否为因数）\n",
    "                    li.append(i)                #将因数 i 加入列列表\n",
    "                    li.append(int(n/i))         #加入 i 所对应的另一个因数\n",
    "            li = list(set(li))                  #去个重（i恰好为平方根时会重复）\n",
    "            # li.sort()                           #排序（可以不用）\n",
    "            return li                           #返回处理好的列表\n",
    "        #print(cf(int(input())))                 #调用\n",
    "\n",
    "        ans=0\n",
    "        for i in nums:\n",
    "            ans+=sum(cf(i)) if len(cf(i))==4 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def cf(n):\n",
    "            li = []                             #创建空列表用于存储因数\n",
    "            for i in range(1, int(n**0.5) + 1): #因数从一开始算，算到原本的数的平方根停止\n",
    "                if n % i == 0:                  #检测是i是否能被n整除（是否为因数）\n",
    "                    li.append(i)                #将因数 i 加入列列表\n",
    "                    li.append(int(n/i))         #加入 i 所对应的另一个因数\n",
    "            li = list(set(li))                  #去个重（i恰好为平方根时会重复）\n",
    "            li.sort()                           #排序（可以不用）\n",
    "            return li                           #返回处理好的列表\n",
    "        #print(cf(int(input())))                 #调用\n",
    "\n",
    "        ans=0\n",
    "        for i in nums:\n",
    "            ans+=sum(cf(i)) if len(cf(i))==4 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            p = 2\n",
    "            count = 2\n",
    "            temp = i + 1\n",
    "            while p * p <= i:\n",
    "                if p*p == i:\n",
    "                    count += 1\n",
    "                    break\n",
    "                if i % p == 0:\n",
    "                    count += 2\n",
    "                    temp += p\n",
    "                    temp += i // p\n",
    "                p += 1\n",
    "            if count == 4:\n",
    "                ans += temp\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            if i / int(math.sqrt(i)) == int(math.sqrt(i)):\n",
    "                continue\n",
    "            divisors = []\n",
    "            for j in range(1, int(math.sqrt(i) + 1)):\n",
    "                if i % j == 0:\n",
    "                    divisors.append(j)\n",
    "                    divisors.append(i // j)\n",
    "            if len(divisors) == 4:\n",
    "                for j in divisors:\n",
    "                    ans += j\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            # factor_cnt: 因数的个数\n",
    "            # factor_sum: 因数的和\n",
    "            factor_cnt = factor_sum = 0\n",
    "            i = 1\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    factor_cnt += 1\n",
    "                    factor_sum += i\n",
    "                    if i * i != num:   # 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数\n",
    "                        factor_cnt += 1\n",
    "                        factor_sum += num // i\n",
    "                i += 1\n",
    "            if factor_cnt == 4:\n",
    "                ans += factor_sum\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "def issiyin(num):\n",
    "    if num < 6:\n",
    "        return 0\n",
    "    res = []\n",
    "    mid = math.sqrt(num)\n",
    "    mid = int(mid)\n",
    "    for i in range(2,mid+1):\n",
    "        a,b = divmod(num,i)\n",
    "        if b == 0:\n",
    "            if i not in res:\n",
    "                res.append(i)\n",
    "            if a not in res:\n",
    "                res.append(a)\n",
    "    if len(res) == 2:\n",
    "        return 1+num+sum(res)\n",
    "    return 0\n",
    "        \n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans += issiyin(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            factors = 0\n",
    "            sums = 0\n",
    "            for i in range(1, int(math.sqrt(x)) + 1):\n",
    "                if x % i == 0:\n",
    "                    sums += i \n",
    "                    factors += 1\n",
    "                    if i * i < x:\n",
    "                        sums += x // i \n",
    "                        factors += 1\n",
    "                i+=1\n",
    "            #print(x, factors, sums)\n",
    "            if factors == 4:\n",
    "                ans += sums \n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def four(n):\n",
    "            count=2\n",
    "            sum_=0\n",
    "            i=2\n",
    "            while i**2<=n:\n",
    "                if n%i==0:\n",
    "                    if i*i==n:\n",
    "                        count+=1\n",
    "                        sum_+=i\n",
    "                    else:\n",
    "                        count+=2\n",
    "                        sum_+=(i+n//i)\n",
    "                if count>4:\n",
    "                    return 0\n",
    "                i+=1\n",
    "            if count==4:\n",
    "                return sum_+1+n\n",
    "            return 0\n",
    "        res=0\n",
    "        for num in nums:\n",
    "            res+=four(num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def get_divisors(x: int) -> list[int]:\n",
    "            d = []\n",
    "            i = 1\n",
    "            while i <= x // i:\n",
    "                if x % i == 0:\n",
    "                    d.append(i)\n",
    "                    if i != x // i: d.append(x // i)\n",
    "                i += 1\n",
    "            return d\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            divisors = get_divisors(n)\n",
    "            if len(divisors) == 4:\n",
    "                res += sum(divisors)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            cnt = 0\n",
    "            s = 0\n",
    "            i = 1\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    cnt += 1\n",
    "                    s += i\n",
    "                    if i * i != x:\n",
    "                        cnt += 1\n",
    "                        s += x // i\n",
    "                i += 1\n",
    "            if cnt == 4:\n",
    "                ans += s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def Pri(self,n):\n",
    "        sum = 0\n",
    "        res = 0\n",
    "        for i in range(1,int(sqrt(n))+1):\n",
    "            if n % i == 0:\n",
    "                res+=2\n",
    "                sum+=i\n",
    "                sum += (n//i)\n",
    "            if(i*i == n):\n",
    "                res-=1\n",
    "        return sum if res==4 else 0\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum += self.Pri(nums[i])\n",
    "        return sum\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            divisors = set()\n",
    "            for i in range(1, int(num ** 0.5) + 1):\n",
    "                if num % i == 0:\n",
    "                    divisors.add(i)\n",
    "                    divisors.add(num // i)\n",
    "                    if len(divisors) > 4:\n",
    "                        break\n",
    "            if len(divisors) == 4:\n",
    "                result += sum(divisors)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "class Solution:\n",
    "    def isValid(self,num):\n",
    "        res = []\n",
    "        for i in range(1,int(sqrt(num))+1):\n",
    "            if num%i == 0:\n",
    "                res.append(i)\n",
    "                if num//i not in res:\n",
    "                    res.append(num//i)\n",
    "        if len(res) == 4:\n",
    "            # print(res)\n",
    "            return sum(res)\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans += self.isValid(num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def products(n):\n",
    "            ct=0\n",
    "            result1 = [1,n]\n",
    "            t1, t2 = -1, -1\n",
    "            for i in range(2,int(math.sqrt(n)+1)):\n",
    "                if ct>4:return 0\n",
    "                if n % i == 0:\n",
    "                    if t1 == n // i and t2 == i:\n",
    "                        break\n",
    "                    else:\n",
    "                        if result1.count(i) == 0:\n",
    "                            ct+=1\n",
    "                            result1.append(i)\n",
    "                        if result1.count(n // i) == 0:\n",
    "                            ct += 1\n",
    "                            result1.append(n // i)\n",
    "\n",
    "                        t1, t2 = i, n // i\n",
    "                        if t1 == t2:\n",
    "                            break\n",
    "            if len(result1) == 4:\n",
    "                return sum(result1)\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        r=0\n",
    "        for i in range(len(nums)):\n",
    "            r+=products(nums[i])\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            a = int(sqrt(i))\n",
    "            if a*a==i:\n",
    "                continue\n",
    "            cur = cnt = 0\n",
    "            for j in range(1, a+1):\n",
    "                if not i%j and i//j!=j:\n",
    "                    cur += j+i//j\n",
    "                    cnt += 1\n",
    "            if cnt==2:\n",
    "                res+=cur\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        # for i in range(n):\n",
    "        for num in nums:\n",
    "            sset=set()\n",
    "            for i in range(1,int(math.sqrt(num)+1)):\n",
    "                if num%i==0:\n",
    "                    sset.add(num//i)\n",
    "                    sset.add(i)\n",
    "            if len(sset)==4:\n",
    "                for s in sset:\n",
    "                    ans+=s\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def help(x):\n",
    "            cnt = 0\n",
    "            res = []\n",
    "            for i in range(1, int(sqrt(x))+1):\n",
    "                if x % i == 0:\n",
    "                    if i * i == x:\n",
    "                        res.append(i)\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        res.extend([i, x // i])\n",
    "                        cnt += 2\n",
    "                    if cnt > 4:\n",
    "                        return []\n",
    "            return [] if cnt != 4 else res\n",
    "        \n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            tmp = help(num)\n",
    "            if len(tmp) > 0:\n",
    "                res += sum(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fact(self,x):\n",
    "        \n",
    "        res=[]\n",
    "        for i in range(1,int(x**0.5)+1):\n",
    "            if(x%i==0):\n",
    "                res+=[i,x//i]\n",
    "\n",
    "        \n",
    "        return set(res)\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        t=0\n",
    "        for i in nums:\n",
    "            res=self.fact(i)\n",
    "            if(len(res)==4):\n",
    "                t+=sum(res)\n",
    "        return t\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            factors = 2\n",
    "            sums = 1 + x\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    sums += i \n",
    "                    factors += 1\n",
    "                    if i * i < x:\n",
    "                        sums += x // i \n",
    "                        factors += 1\n",
    "                i+=1\n",
    "            #print(x, factors, sums)\n",
    "            if factors == 4:\n",
    "                ans += sums \n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def get_factors(num):\n",
    "            factors = set()\n",
    "            for i in range(1, int(num**0.5) + 1):\n",
    "                if num % i == 0:\n",
    "                    factors.add(i)\n",
    "                    factors.add(num // i)\n",
    "                    if len(factors) > 4:\n",
    "                        return set()\n",
    "            return factors\n",
    "\n",
    "        result_sum = 0\n",
    "\n",
    "        for num in nums:\n",
    "            factors = get_factors(num)\n",
    "            if len(factors) == 4:\n",
    "                result_sum += sum(factors)\n",
    "\n",
    "        return result_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        dic={}\n",
    "        nums.sort()\n",
    "\n",
    "        for num in nums:\n",
    "            cnt=0\n",
    "            s=0\n",
    "            i=1\n",
    "            while i*i<=num:\n",
    "                if num%i==0:\n",
    "                    cnt+=1\n",
    "                    s=s+i\n",
    "                    if cnt>4:\n",
    "                        break\n",
    "                    if i*i!=num:\n",
    "                        cnt+=1\n",
    "                        s+=num//i\n",
    "                i=i+1\n",
    "            if cnt==4:\n",
    "                ans+=s\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def cf(n):\n",
    "            li = []                             #创建空列表用于存储因数\n",
    "            for i in range(1, int(n**0.5) + 1): #因数从一开始算，算到原本的数的平方根停止\n",
    "                if n % i == 0:                  #检测是i是否能被n整除（是否为因数）\n",
    "                    li.append(i)                #将因数 i 加入列列表\n",
    "                    li.append(int(n/i))         #加入 i 所对应的另一个因数\n",
    "            li = list(set(li))                  #去个重（i恰好为平方根时会重复）\n",
    "            # li.sort()                           #排序（可以不用）\n",
    "            return li                           #返回处理好的列表\n",
    "        #print(cf(int(input())))                 #调用\n",
    "\n",
    "        ans=0\n",
    "        for i in nums:\n",
    "            ans+=sum(cf(i)) if len(cf(i))==4 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def cf(n):\n",
    "            li = []                             #创建空列表用于存储因数\n",
    "            for i in range(1, int(n**0.5) + 1): #因数从一开始算，算到原本的数的平方根停止\n",
    "                if n % i == 0:                  #检测是i是否能被n整除（是否为因数）\n",
    "                    li.append(i)                #将因数 i 加入列列表\n",
    "                    li.append(int(n/i))         #加入 i 所对应的另一个因数\n",
    "            li = list(set(li))                  #去个重（i恰好为平方根时会重复）\n",
    "            #li.sort()                           #排序（可以不用）\n",
    "            return li                           #返回处理好的列表\n",
    "        #print(cf(int(input())))                 #调用\n",
    "\n",
    "        ans=0\n",
    "        for i in nums:\n",
    "            ans+=sum(cf(i)) if len(cf(i))==4 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        counter = Counter(nums)\n",
    "        res = 0\n",
    "        for num, count in counter.items():\n",
    "            factors = set()\n",
    "            for i in range(1, int(math.sqrt(num)) + 1):\n",
    "                if num % i == 0:\n",
    "                    factors.add(i)\n",
    "                    factors.add(num // i)\n",
    "                if len(factors) > 4:\n",
    "                    break\n",
    "            if len(factors) == 4:\n",
    "                res += count * sum(factors)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        def divsum(num):\n",
    "            res = []\n",
    "            n = math.sqrt(num)\n",
    "            for i in range(1,floor(n)+1,1):\n",
    "                if (num%i==0):\n",
    "                    if(i*i != num):\n",
    "                        res.append(i)\n",
    "                        res.append(num//i)\n",
    "                    else:\n",
    "                        res.append(i)\n",
    "            print(res)\n",
    "            if len(res) == 4:\n",
    "                return sum(res)\n",
    "            else:\n",
    "                return 0\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            res+=divsum(i)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            p = 2\n",
    "            count = 2\n",
    "            temp = i + 1\n",
    "            while p * p <= i:\n",
    "                if p*p == i:\n",
    "                    count += 1\n",
    "                    break\n",
    "                if i % p == 0:\n",
    "                    print(p)\n",
    "                    count += 2\n",
    "                    temp += p\n",
    "                    temp += i // p\n",
    "                p += 1\n",
    "            if count == 4:\n",
    "                ans += temp\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        print(6**0.5)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            found = 0\n",
    "            tmp = -1\n",
    "            for i in range(2,int(num**0.5)+1):\n",
    "                \n",
    "                if num%i==0:\n",
    "                    if i==num**0.5:\n",
    "                        found+=1\n",
    "                    found += 2\n",
    "                    tmp = i\n",
    "            if found==2:\n",
    "                print(num)\n",
    "                res += tmp+(num//tmp)+num+1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def get_sum(n):\n",
    "            ans = set()\n",
    "            for i in range(1, isqrt(n) + 1):\n",
    "                if n // i * i == n:\n",
    "                    ans.update((i, n // i))\n",
    "                    if len(ans) > 4:\n",
    "                        return 0\n",
    "            if len(ans) == 4:\n",
    "                return sum(ans)\n",
    "            return 0\n",
    "\n",
    "        return sum(map(get_sum, nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def fun(x):\n",
    "            res = 2;st = 1+x\n",
    "            t = int(sqrt(x))\n",
    "            if t*t == x:\n",
    "                return 0\n",
    "            for i in range(2,t+1):\n",
    "                if x%i == 0:\n",
    "                    st += i + x//i\n",
    "                    res += 2\n",
    "                    if res > 4:return 0\n",
    "            return st if res == 4 else 0\n",
    "        return sum(fun(x) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        for num in nums:\n",
    "            zhongjiandeshuzi = num** 0.5\n",
    "            if zhongjiandeshuzi==int(zhongjiandeshuzi):\n",
    "                continue\n",
    "            else:\n",
    "                zhongjiandeshuzi= int(zhongjiandeshuzi)+1\n",
    "\n",
    "            # print(int(zhongjiandeshuzi),22222222)\n",
    "            yinsus=[]\n",
    "            for i in range(2, int(zhongjiandeshuzi)):\n",
    "                if num%i==0:\n",
    "                    yinsus.append(i)\n",
    "                if len(yinsus)>=2:\n",
    "                    break\n",
    "            if len(yinsus)==1:\n",
    "                # print(num,111111)\n",
    "                res+=1\n",
    "                res+=num\n",
    "                res+=yinsus[0]\n",
    "                res+= (num // yinsus[0])\n",
    "                print(res,33333333)\n",
    "        \n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def get_all_factor(num):\n",
    "            factor = set()\n",
    "            for i in range(1, int(math.sqrt(num)) +1):\n",
    "                if num %i == 0:\n",
    "                    factor.add(i)\n",
    "                    factor.add(num//i)\n",
    "                if len(factor) > 4:\n",
    "                    return 0\n",
    "            if len(factor) == 4:\n",
    "                return sum(factor)\n",
    "            return  0\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res +=get_all_factor(nums[i])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\r\n",
    "        c = Counter(nums)\r\n",
    "        sum = 0\r\n",
    "        for k,v in c.items():\r\n",
    "            cnt = 0\r\n",
    "            t = 0\r\n",
    "            for i in range(1, int(math.sqrt(k))+1):\r\n",
    "                if k % i == 0:\r\n",
    "                    cnt += 1\r\n",
    "                    t += i\r\n",
    "                    if k // i != i:\r\n",
    "                        cnt += 1\r\n",
    "                        t += k // i\r\n",
    "            if cnt == 4:\r\n",
    "                sum += t * v\r\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sumFourDivisors(self, nums) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            upper = nums[0]\n",
    "        else:\n",
    "            upper = max(*nums)\n",
    "        # 首先在这里筛选素数\n",
    "        isPrim = [True for _ in range(upper)]\n",
    "        i = 2\n",
    "        while i * i < upper:\n",
    "            if isPrim[i]:\n",
    "                j = i * i\n",
    "                while j < upper:\n",
    "                    isPrim[j] = False\n",
    "                    j += i\n",
    "            i += 1\n",
    "        # 把素数都提取出来\n",
    "        prims = [i for i in range(2, upper) if isPrim[i]]\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            for prim in prims:\n",
    "                # 已经不可能了，后续不算了\n",
    "                if prim * prim > num:\n",
    "                    break\n",
    "                # 立方数是符合的，这个比较坑，开始没想到，比如 8\n",
    "                if prim * prim * prim == num:\n",
    "                    ans += (1 + num + prim + prim * prim)\n",
    "                    break\n",
    "                # 可以分解成两个质数乘积\n",
    "                if num % prim == 0 and isPrim[num // prim] and prim * prim != num:\n",
    "                    ans += (1 + num + prim + num // prim)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        mx = max(nums)\n",
    "        if mx <= 5: return 0\n",
    "        n = int(sqrt(mx))\n",
    "        has, ss = [0] * mx, []\n",
    "        has[0] = has[1] = 1\n",
    "        for i in range(2, mx):\n",
    "            if has[i] == 0:\n",
    "                if i <= n: ss.append(i)\n",
    "                ni = i * 2\n",
    "                while ni < mx:\n",
    "                    has[ni] = 1\n",
    "                    ni += i\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            for j in ss:\n",
    "                if j * j >= i: break\n",
    "                if i % j == 0:\n",
    "                    x = i // j\n",
    "                    if x < mx and (has[x] == 0 or x == j*j):\n",
    "                        res += x + j + i + 1\n",
    "                        break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sumFourDivisors(self, nums) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            upper = nums[0]\n",
    "        else:\n",
    "            upper = max(*nums)\n",
    "        # 首先在这里筛选素数\n",
    "        isPrim = [True for _ in range(upper)]\n",
    "        i = 2\n",
    "        while i * i < upper:\n",
    "            if isPrim[i]:\n",
    "                j = i * i\n",
    "                while j < upper:\n",
    "                    isPrim[j] = False\n",
    "                    j += i\n",
    "            i += 1\n",
    "        # 把素数都提取出来\n",
    "        prims = [i for i in range(2, upper) if isPrim[i]]\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            for prim in prims:\n",
    "                # 已经不可能了，后续不算了\n",
    "                if prim * prim > num:\n",
    "                    break\n",
    "                # 立方数是符合的，这个比较坑，开始没想到，比如 8\n",
    "                if prim * prim * prim == num:\n",
    "                    ans += (1 + num + prim + prim * prim)\n",
    "                    break\n",
    "                # 可以分解成两个质数乘积\n",
    "                if num % prim == 0 and isPrim[num // prim] and prim * prim != num:\n",
    "                    ans += (1 + num + prim + num // prim)\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@lru_cache(None)\n",
    "def get_all_factor(num):\n",
    "    factor = set()\n",
    "    for i in range(1, int(math.sqrt(num)) + 1):\n",
    "        if num % i == 0:\n",
    "            factor.add(i)\n",
    "            factor.add(num // i)\n",
    "        if len(factor) > 4:\n",
    "            return 0\n",
    "    return sum(factor) if len(factor) == 4 else 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        return sum(get_all_factor(num) for num in nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 10 ** 5 + 1\n",
    "primes = []\n",
    "is_prime = [True] * mx\n",
    "for i in range(2, mx):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "    for p in primes:\n",
    "        if p * i >= mx: break\n",
    "        is_prime[p * i] = False\n",
    "        if i % p == 0: break\n",
    "n = len(primes)\n",
    "four = Counter()\n",
    "for i in range(n - 1):\n",
    "    if primes[i] >= 317:\n",
    "        break \n",
    "    for j in range(i + 1, n):\n",
    "        if primes[i] * primes[j] >= 10 ** 5:\n",
    "            break \n",
    "        four[primes[i] * primes[j]] = primes[i] + primes[j] + 1 + primes[i] * primes[j]\n",
    "for i in range(n - 1):\n",
    "    if primes[i] ** 3 >= 10 ** 5:\n",
    "        break \n",
    "    four[primes[i] ** 3] = 1 + primes[i] + primes[i] ** 2 + primes[i] ** 3\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            ans += four[i]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "pt=PrimeTable(10**5)\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        for n in nums:\n",
    "            f=pt.get_factors(n)\n",
    "            if len(f)==4:\n",
    "                res+=sum(f)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        # C 是数组 nums 元素的上限，C3 是 C 的立方根\n",
    "        C, C3 = 100000, 46\n",
    "\n",
    "        isprime = [True] * (C + 1)\n",
    "        primes = list()\n",
    "\n",
    "        # 埃拉托斯特尼筛法\n",
    "        for i in range(2, C + 1):\n",
    "            if isprime[i]:\n",
    "                primes.append(i)\n",
    "            for j in range(i + i, C + 1, i):\n",
    "                isprime[j] = False\n",
    "        \n",
    "        # 欧拉筛法\n",
    "        \"\"\"\n",
    "        for i in range(2, C + 1):\n",
    "            if isprime[i]:\n",
    "                primes.append(i)\n",
    "            for prime in primes:\n",
    "                if i * prime > C:\n",
    "                    break\n",
    "                isprime[i * prime] = False\n",
    "                if i % prime == 0:\n",
    "                    break\n",
    "        \"\"\"\n",
    "        \n",
    "        # 通过质数表构造出所有的四因数\n",
    "        factor4 = dict()\n",
    "        for prime in primes:\n",
    "            if prime <= C3:\n",
    "                factor4[prime**3] = 1 + prime + prime**2 + prime**3\n",
    "        for i in range(len(primes)):\n",
    "            for j in range(i + 1, len(primes)):\n",
    "                if primes[i] * primes[j] <= C:\n",
    "                    factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j]\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            if num in factor4:\n",
    "                ans += factor4[num]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        # C 是数组 nums 元素的上限，C3 是 C 的立方根\n",
    "        C, C3 = 100000, 46\n",
    "\n",
    "        isprime = [True] * (C + 1)\n",
    "        primes = list()\n",
    "\n",
    "        # 埃拉托斯特尼筛法\n",
    "        for i in range(2, C + 1):\n",
    "            if isprime[i]:\n",
    "                primes.append(i)\n",
    "            for j in range(i + i, C + 1, i):\n",
    "                isprime[j] = False\n",
    "        \n",
    "        # 欧拉筛法\n",
    "        \"\"\"\n",
    "        for i in range(2, C + 1):\n",
    "            if isprime[i]:\n",
    "                primes.append(i)\n",
    "            for prime in primes:\n",
    "                if i * prime > C:\n",
    "                    break\n",
    "                isprime[i * prime] = False\n",
    "                if i % prime == 0:\n",
    "                    break\n",
    "        \"\"\"\n",
    "        \n",
    "        # 通过质数表构造出所有的四因数\n",
    "        factor4 = dict()\n",
    "        for prime in primes:\n",
    "            if prime <= C3:\n",
    "                factor4[prime**3] = 1 + prime + prime**2 + prime**3\n",
    "        for i in range(len(primes)):\n",
    "            for j in range(i + 1, len(primes)):\n",
    "                if primes[i] * primes[j] <= C:\n",
    "                    factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j]\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            if num in factor4:\n",
    "                ans += factor4[num]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 埃拉托斯特尼筛法 / 欧拉筛法 , 预处理\n",
    "class Solution:\n",
    "    def sumFourDivisors(self, nums: List[int]) -> int:\n",
    "        # C 是数组 nums 元素的上限，C3 是 C 的立方根\n",
    "        C, C3 = 100000, 46\n",
    "\n",
    "        isprime = [True] * (C + 1)\n",
    "        primes = list()\n",
    "\n",
    "        # 埃拉托斯特尼筛法，筛选出素数\n",
    "        for i in range(2, C + 1):\n",
    "            if isprime[i]:\n",
    "                primes.append(i)\n",
    "            for j in range(i + i, C + 1, i):\n",
    "                isprime[j] = False\n",
    "        \n",
    "        # 欧拉筛法\n",
    "        \"\"\"\n",
    "        for i in range(2, C + 1):\n",
    "            if isprime[i]:\n",
    "                primes.append(i)\n",
    "            for prime in primes:\n",
    "                if i * prime > C:\n",
    "                    break\n",
    "                isprime[i * prime] = False\n",
    "                if i % prime == 0:\n",
    "                    break\n",
    "        \"\"\"\n",
    "        \n",
    "        # 通过质数表构造出所有的四因数\n",
    "        factor4 = dict()\n",
    "        for prime in primes:\n",
    "            if prime <= C3:\n",
    "                factor4[prime**3] = 1 + prime + prime**2 + prime**3\n",
    "        for i in range(len(primes)):\n",
    "            for j in range(i + 1, len(primes)):\n",
    "                if primes[i] * primes[j] <= C:\n",
    "                    factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j]\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            if num in factor4:\n",
    "                ans += factor4[num]\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
